﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FC.Math
{
    public class BigInteger
    {
        /// <summary>
        /// 存放数字的列表，每个byte存放两个十进制数
        /// </summary>
        private List<byte> integers;

        /// <summary>
        /// 进位器
        /// </summary>
        private int carry;

        #region 构造函数

        public BigInteger()
        {
            integers = new List<byte>();
            integers.Add(0);
        }

        public BigInteger(string integer) : this()
        {
            integers.Remove(0);
            for (int i=integer.Length - 1; i>=0; i-= 2)
            {
                int j = i - 1;
                if(j >= 0)
                {
                    AddValue(integer[i] - '0', integer[j] - '0');
                }
                else
                {
                    AddValue(integer[i] - '0', 0);
                }
            }
        }

        #endregion

        #region 重载

        /// <summary>
        /// 判断相等
        /// </summary>
        /// <param name="obj"></param>
        /// <returns></returns>
        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        /// <summary>
        /// 获取哈希值
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        /// <summary>
        /// 转化为字符串
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            string result = "";
            for (int i=0; i<integers.Count; i++)
            {
                int a = integers[i] & 15;
                int b = (integers[i] >> 4) & 15;
                result = (i == integers.Count - 1 && b == 0 ? "" : b.ToString()) + $"{a}{result}";
            }
            return result;
        }

        #endregion
        
        #region 运算符重载

        /// <summary>
        /// 加法运算
        /// </summary>
        /// <param name="a">被加数</param>
        /// <param name="b">加数</param>
        /// <returns>和</returns>
        public static BigInteger operator +(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 减法运算
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator -(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 乘法运算
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator *(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 除法运算
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator /(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 取余（取模）运算
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator %(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 判断相等
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator ==(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 判断不相等
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator !=(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 判断大于
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator >(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 判断小于
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator <(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }

        /// <summary>
        /// 大于等于
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator >=(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }
        
        /// <summary>
        /// 小于等于
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static BigInteger operator <=(BigInteger a, BigInteger b)
        {
            return a.Add(b);
        }
        
        /// <summary>
        /// 乘方运算
        /// </summary>
        /// <param name="a">底数</param>
        /// <param name="b">指数</param>
        /// <returns>结果</returns>
        public static BigInteger operator ^(BigInteger a, BigInteger b)
        {
            return a.Power(b);
        }

        #endregion

        #region 运算

        /// <summary>
        /// 加等运算 相当于 +=
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public BigInteger Add(BigInteger other)
        {
            int i = 0;
            for (i = 0; i< integers.Count && i < other.integers.Count; i++)
            {
                SetValue(i, 
                    CountSum(integers[i] & 15, other.integers[i] & 15), 
                    CountSum(integers[i] >> 4 & 15, other.integers[i] >> 4 & 15));
            }
            while (i < integers.Count && carry > 0)
            {
                SetValue(i, 
                    CountSum(integers[i] & 15), 
                    CountSum(integers[i] >> 4 & 15));
                i++;
            }
            while(i < other.integers.Count)
            {
                AddValue(CountSum(other.integers[i] & 15),
                    CountSum(other.integers[i] >> 4 & 15));
                i++;
            }
            if(carry > 0)
            {
                AddValue(CountSum(0), 0);
            }
            return this;
        }

        /// <summary>
        /// 计算 带进位 的 两位数 加法
        /// </summary>
        /// <param name="a">加数</param>
        /// <param name="b">加数</param>
        /// <returns>和</returns>
        private int CountSum(int a, int b = -1)
        {
            int sum = a + carry + (b == -1 ? 0 : b);
            if (sum >= 10)
            {
                sum -= 10;
                carry = 1;
            }
            else carry = 0;
            return sum;
        }

        /// <summary>
        /// 设置值
        /// </summary>
        /// <param name="index">下标</param>
        /// <param name="low">低位</param>
        /// <param name="high">高位</param>
        private void SetValue(int index, int low, int high)
        {
            integers[index] = (byte)((high << 4) + low);
        }

        /// <summary>
        /// 添加一个值
        /// </summary>
        /// <param name="low">低位</param>
        /// <param name="high">高位</param>
        private void AddValue(int low, int high)
        {
            integers.Add((byte)((high << 4) + low));
        }

        /// <summary>
        /// 减法运算
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public BigInteger Subtract(BigInteger other)
        {
            return new BigInteger();
        }

        /// <summary>
        /// 乘法运算
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public BigInteger Multiply(BigInteger other)
        {
            return new BigInteger();
        }

        /// <summary>
        /// 除法运算
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public BigInteger Divide(BigInteger other)
        {
            return new BigInteger();
        }

        /// <summary>
        /// 取余运算（取模）
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        public BigInteger Mod(BigInteger other)
        {
            return new BigInteger();
        }

        /// <summary>
        /// 乘方运算
        /// </summary>
        /// <param name="other"></param>
        /// <returns></returns>
        private BigInteger Power(BigInteger other)
        {
            return new BigInteger();
        }

        #endregion
    }
}
